/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 *        1
 *      /   \
 *     2     3
 *    / \   / \
 *   4   5 6   7
 */

/**
 * 先序遍历，根左右，所以先把变成 根右左 顺序入栈
 * @param {} tree 
 */
var preorder = function(tree) {
  let result = [];
  let stack = [];
  stack.push(tree);
  while(stack.length != 0) {
    let node = stack.pop();
    result.push(node.val);
    if(node.right) {
      stack.push(node.right);
    }
    if(node.left) {
      stack.push(node.left);
    }
  }
  console.log(result)
}

// 左根右
var midorderTraverse = function(tree) {
  let result = [];
  let stack = [];
  let node = tree;
  while(stack.length || node) {
    // 一直往左找子节点，第一轮入栈，没有左节点后 if条件结束
    if(node) {
      stack.push(node);
      node = node.left;
    } else {
      // 出栈，此时是从最左侧节点开始出栈 顺序是 4 此时node为null了，继续出2，node.right有值，进入循环
      // 5入栈，node.left为null，进入出栈逻辑，此时5出栈 4 2 5，node.right为null，出栈 4 2 5 1
      // 1的right不为空，又将3入栈，node.left 6入栈，node为null，开始出栈
      // 6出栈，node=null，3出栈，node.right=7，入栈，node=null，出栈 7 结果即为4 2 5 1 6 3 7
      node = stack.pop();
      result.push(node.val);
      // 找该节点的右子节点
      node = node.right;
    }
  }
  console.log(result)
}

// 左右根 ，双栈
var afterorderTranverse = function(tree) {
  let result = [];
  let stack1 = [tree];
  let stack2 = [];
  while(stack1.length) {
    let node = stack1.pop();
    stack2.push(node);
    if(node.left) {
      stack1.push(node.left)
    }
    if(node.right) {
      stack1.push(node.right);
    }
  }
  while(stack2.length) {
    let node = stack2.pop();
    result.push(node.val);
  }
  console.log(result)
}

var tree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4
    },
    right: {
      val: 5
    }
  },
  right: {
    val: 3,
    left: {
      val: 6
    },
    right: {
      val: 7
    }
  }
}

// levelTraversal(tree);
// preorder(tree);
midorderTraverse(tree);
afterorderTranverse(tree);